package bTree.LeetCode;

public class 下降路径最小和 {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp;
        if (n == 1) {
            return matrix[0][0];
        } else if (n == 2) {
            return Math.min(matrix[0][0], matrix[0][1]) + Math.min(matrix[1][0], matrix[1][1]);
        } else {
            dp = new int[n][n];
            for (int i = 0; i < n; i++) {
                dp[0][i] = matrix[0][i];
            }
            for (int i = 1; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (j == 0) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];
                    } else if (j == n - 1) {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j];
                    } else {
                        int min1 = Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
                        int min = Math.min(min1, dp[i - 1][j + 1]);
                        dp[i][j] = min + matrix[i][j];
                    }
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i : dp[n - 1]) {
            min = Math.min(min, i);
        }
        return min;
    }
}